package simple;

import java.util.Objects;

/**
 * 实现strStr()函数。
 *
 * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
 * 说明：
 *
 * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 *
 * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
 *
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ImplementStr {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.strStr("mississippi", "issip");
    }

    static class Solution {
        public int strStr(String haystack, String needle) {
            if(Objects.isNull(needle) || needle.length() == 0){
                return 0;
            }
            int p = 0;
            int s = 0;
            int[] nextArr = buildNextArr(needle);
            while(p < haystack.length() && s < needle.length()){
                if(0 > s || haystack.charAt(p) == needle.charAt(s)){
                    s++;
                    p++;
                }else{
                    s = nextArr[s];
                }
            }
            return s == needle.length() ? p - s : -1;
        }

        int[] buildNextArr(String needle){
            int left = -1;
            int right = 0;
            int[] nextArr = new int[needle.length()];
            nextArr[0] = -1;
            while (right < needle.length()-1){
                if(0 > left || needle.charAt(right) == needle.charAt(left)){
                    left++;
                    right++;
                    nextArr[right] = left;
                }else{
                    left = nextArr[left];
                }
            }
            return nextArr;
        }
    }
}
